package algorithm.leetcode.I1to100;

import java.util.*;

public class Q18 {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();
        Map<String, List<Integer>> map = new HashMap<>();

        if (nums.length < 4) return res;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            for (int j = i+1; j < nums.length-2; j++) {
                if (j == i+1 || nums[j] > nums[i]) {
                    int k = j+1, l = nums.length-1;

                    while (k < l) {
                        if (nums[i]+nums[j]+nums[k]+nums[l] == target) {
                            List<Integer> temp = new LinkedList<>(Arrays.asList(nums[i],nums[j],nums[k],nums[l]));
                            map.put(temp.stream().map(Objects::toString).reduce((o1, o2) -> o1+o2).get().toString(), temp);
                            k++;
                            l--;
                        }
                        else if (nums[i]+nums[j]+nums[k]+nums[l] < target) k++;
                        else l--;
                    }
                }
            }
        }

        map.forEach((key, value) -> res.add(value));
        return res;
    }

    public List<List<Integer>> fourSum2(int[] nums, int target) {
        List<List<Integer>> res = new LinkedList<>();

        if (nums.length < 4) return res;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length-3; i++) {
            if (i == 0 || nums[i-1] < nums[i]) {
                for (int j = i+1; j < nums.length-2; j++) {
                    if (j == i+1 || nums[j] > nums[j-1]) {
                        int k = j+1, l = nums.length-1;

                        while (k < l) {
                            if (nums[i]+nums[j]+nums[k]+nums[l] == target
                                    && (k == j+1 || nums[k-1] < nums[k])
                                    && (l == nums.length-1 || nums[l+1] > nums[l])) {
                                List<Integer> temp = new LinkedList<>(Arrays.asList(nums[i],nums[j],nums[k],nums[l]));
                                res.add(temp);
                                k++;
                                l--;
                            }
                            else if (nums[i]+nums[j]+nums[k]+nums[l] < target) k++;
                            else l--;
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Q18 q18 = new Q18();
        int[] ints = {-2,-1,-1,1,1,2,2};
        System.out.println(q18.fourSum2(ints, 0));
        // List<Integer> temp = new LinkedList<>(Arrays.asList(-1,-2,-3,54));
        // System.out.println(temp.stream().map(Objects::toString).reduce((o1, o2) -> o1+o2).get().toString());

    }
}
